\section{Knapsack 1}
\subsection*{题意}
经典01背包问题。有 $n$ 个物品，每个物品有重量 $w_i$ 和价值$v_i$。背包的容量为 $W$，换句话说，可以放进背包的物品的重量总和不能超过 $W$。请选择若干物品放入背包并且最大化被选取物品的价值总和。
\subsection*{数据范围}
\begin{itemize}
\item $1 \leq n \leq 100$
\item $1 \leq W \leq 10^5$
\item $1 \leq v_i \leq 10^9$
\end{itemize}
\subsection*{题解}

我们设 {${\texttt{dp}[i][j]}$} 表示\textbf{``只考虑前$i$ 个物品的情况下，背包容量是 $j$所能凑出的最大价值之和"}。那么在计算${\texttt{dp}[i][j]}$的时候，所有情况可以分成两类考虑，
\begin{enumerate}
    \item \textbf{拿第 $i$ 件物品}，那么现在背包容量只剩下 $j - w_i$，而由于每样物品只能拿一件，所以我们只需要考虑前 $i-1$ 件物品的最优选取方式，即最终价值为 $\texttt{dp}[i-1][j-w_i] + v_i$。
    \item \textbf{不拿第 $i$ 件物品}，那么背包容量仍然是 $j$。由于我们选择不拿第$i$件物品，现在只需要考虑前 $i-1$ 件物品的最优选取方式，即最终价值为 ${\texttt{dp}[i-1][j]}$。
\end{enumerate}

所以可以得到转移方程为：

\begin{equation*}
{\texttt{dp}[i][j]} = 
\begin{cases}
 0 & i = 0\\
\max({\texttt{dp}}[i-1][j-w_i] + v_i,{\texttt{dp}}[i-1][j]) & i \ge 1\\
\end{cases}
\end{equation*}

递推或记忆化搜索的复杂度均为 $O(nW)$。


\subsection*{核心代码}
\inputminted[linenos,autogobble]{cpp}{./Code/D.cpp}
\newpage